The present invention relates to the general subject matter of optical mark recognition (xe2x80x9cOMRxe2x80x9d, hereinafter), and more particularly, to methods and apparatus for automatic recognition of when a hand-drawn mark has been made within a particular region of a user-completed document such as a standardized test form.
The use of machine readable forms has been steadily increasing in popularity for obvious reasons, perhaps the foremost of which is that these devices provide a means of automatically gathering very large numbers of human responses. A common scenario involves a user being asked to make (pencil) marks in specific regions of a pre-printed form in order to designate answers to various queries. The form containing the user""s pencil marks is then later xe2x80x9creadxe2x80x9d or scored via some sort of computer-assisted process which determines which responses the user has designated and tabulates those responses for later reporting. Of course, most people are introduced to machine-readable forms when they take their first xe2x80x9cstandardized testxe2x80x9d, wherein the user fills in xe2x80x9cbubblesxe2x80x9d to signify which answer to a multiple choice question is felt to be correct. However, this same technology is useful in many other fields including use in reading survey questionnaires, census data, inventory control, market research, and many others.
Key to the development of this industry has been the continuous improvement in hardware and software that make the machine-reading of a piece of paper bearing marks made by a human a relatively reliable prospect. In a typical application there may be as many hundreds or even thousands of forms that are loaded into a xe2x80x9chopperxe2x80x9d or other receptacle that feeds the form reader. Thus, it is imperative that the process of reading the marks be as reliable as possible.
The process of reading a user-marked form conventionally begins with careful registration of the form that is to be read. At the outset, the registration step is purely a mechanical one. A specialized form reader seizes each form in turn and then positions itxe2x80x94as nearly as is possiblexe2x80x94in precisely the same position so that the various fields on the form are in predetermined locations. Generally speaking, prior art devices require a high degree of accuracy in the initial placement of the form as a prerequisite to their working effectively.
As a next step, the form is converted to a digital format by optical scanning. The conventional arrangement calls for the scanner to be two-level or bi-level scanner, sensing only either xe2x80x9cwhitexe2x80x9d or xe2x80x9cblackxe2x80x9d pixels on the form. It has not been customary for the scan to be in color or gray scale, as the object is to determine whether or not a mark is present and a two-level scan is adequate for that purpose.
Obviously, if the form has been accurately registered and oriented, the optical scanner need only xe2x80x9clookxe2x80x9d in those specific locations on the form where the user has been directed to make marks (xe2x80x9cactive areasxe2x80x9d, hereinafter) in order to find the user""s responses. However, it is not uncommon for there to be some small amount of inaccuracy in the physical placement of the form within the reader. For example, the form might be slightly shifted in one or both lateral dimensions (i.e., horizontal and vertical), or even stretched or rotated. Thus, it is conventional to take some form of corrective action after the form has been converted to digital values in order align it.
Many existing systems require the use of specialized xe2x80x9cregistration marks,xe2x80x9d (also known as xe2x80x9cfiducialxe2x80x9d marks) which are intended to be easily recognized and which have been printed on the form at precisely predetermined locations. When these marks are present on the form, computer algorithms can then be used to examine the digital representation of the form and locate these marks, assuming that they can be located. Given the actual location of the registration marks on the scanned image and a different desired location, mathematical transformations may be used to digitally reorient the form within the computer so the active areas coincide with those of a perfectly registered form. Alternatively, the scanned form maybe left uncorrected and this same sort of transformation used to calculate where the active areas actually may be found on the form as-read.
Even if the active regions on the form have been accurately determined, the process of xe2x80x9creadingxe2x80x9d the mark is not as simple as it might seem. Bubbles might be partially filled or filled completely and lightly or darkly colored. Further, imperfect erasures on the form can be confused with the intended mark so differentiating between those (and other extraneous) marks is a high priority.
The current state-of-the-art in automatic grading begins with the preparation of the forms, which must be printed with extreme precision: conventional laser printing is not usually precise enough. The printed text and bubbles must be accurately located with respect to the edges of the form and with respect to each other. This is because even slight variations in the locations of the printed bubbles can make it difficult if not impossible for an automatic scoring system to later read the user""s answers. A further requirement of current methods of mark detection is that the form be precisely aligned before it is scanned into memory, so that the resulting scanned image has bubbles located in highly predictable locations.
In some instances, special inks are used to print the form (so-called xe2x80x9cdrop-out inksxe2x80x9d) which become effectively xe2x80x9cinvisiblexe2x80x9d when scanned using light at certain wavelengths (e.g., infrared light). Then, when the form is subsequently scanned using light of the appropriate wavelength, the printed form appears nearly invisible, and only the user""s marks effectively remain. However, use of specialized inks can dramatically increase the complexity and cost of printing the forms. Obviously, there would an economic advantage to a method of OMR that could work reliably with conventional printers, inks, and scanners.
Further, the prior art methods of automated scoring/grading of tests involve the use of expensive specialized scanning devices that automatically sense the edges of each page and then mechanically move that page into proper position before it is scanned. Thus, when the form is scanned, the scoring software should always know exactly where each bubble or other response region may be found. However, these specialized machines are expensive and subject to mechanical failure.
Still further, even if the marked form has been correctly registered and scanned, reading the marks thereon may still represent a significant challenge. For example, even something as conceptually simple as locating a specific response region (e.g., bubble) on the scanned form is complicated by the fact that the bubble could potentially be offset from its theoretical location by a few pixels, even if everything is accurately registered. Additionally, differentiating the form""s printed background information from the user""s mark, differentiating lightly marked selections from erasures, and a host of other practical problems stand in the way of anyone who would seek to develop a system of automatically scoring these sorts of tests.
Heretofore, as is well known in the optical mark recognition arts, there has been a need for an invention to address and solve the above-described problems. Accordingly, it should now be recognized, as was recognized by the present inventor, that there exists, and has existed for some time, a very real need for a device that would address and solve the above-described problems.
Before proceeding to a description of the present invention, however, it should be noted and remembered that the description of the invention which follows, together with the accompanying drawings, should not be construed as limiting the invention to the examples (or preferred embodiments) shown and described. This is so because those skilled in the art to which the invention pertains will be able to devise other forms of this invention within the ambit of the appended claims.
There is provided hereinafter a new method of identifying when a particular hand-drawn selection has been made on, for example, a standardized test form. This method does not require the use of any particular form design nor does it use registration marks. It is robust enough to be used when the form is somewhat misaligned on the scanning device.
According to a first aspect of the instant invention, there is provided a method of reading or determining the mark sense of a user-marked form, which begins by storing in computer memory or hard disk a digital image of a blank copy of the form which the user has been asked to mark. In the preferred embodiment, the digital image will be a high-resolution color (e.g., 8 bit) scan of the form which has been obtained by scanning a blank form.
As a next step, a user-marked form is obtained in digital form. Preferably, this also will be a high-resolution color scan of the marked form which has been scanned at the same resolution as the blank form.
Then, the digital version of the user-marked form is mathematically xe2x80x9cshiftedxe2x80x9d to make it correspond as closely as possible to the orientation of the scanned blank form. The preferred method of doing this utilizes an iterative procedure, wherein successively higher resolution versions of the two forms are used at each iteration, where the term xe2x80x9cresolutionxe2x80x9d is used herein in its broadest sense to refer to varying levels of information content in the scanned image. Methods of obtaining versions of an image at a variety of different xe2x80x9cresolutionsxe2x80x9d are discussed hereinafter. At the final step, the calculated image shift should only amount to a few pixels.
The instant method continues by selecting a first field (e.g., a xe2x80x9cbubblexe2x80x9d on the form) to examine. The bubble is found at a known location on the scanned-blank form and its location is known at least approximately on the user-marked form. Then, the small region of the user""s form containing the bubble (which may or may not contain a user mark) is locally realigned to make it match as nearly as possible the alignment of the standard (blank) bubble. This prepares the user-scanned form for use in the steps that follow.
In the preferred embodiment, the next step involves the calculation and application of an optional intensity variance adjustment, which is designed to correct for a common defect that can be introduced by high-speed scanners. Preferably, the adjustment is effected by comparing the mean image intensity/brightness in two or more corresponding regions in the scanned blank and user-marked forms. Using the brightness of the corresponding portions of the two images, a transformation is mathematically determined that is designed to smoothly correct for observed differences in overall image intensity. The intensity correction is preferably interpolated in areas between the reference regions.
Finally, once the two bubbles are in the best possible alignment and the image intensities are comparable, a score is calculated that reflects the degree of similarity between the unmarked bubble (from the reference image) and the potentially marked bubble. Based on this objectively calculated value, a determination is made as to whether or not the form as been marked. Additionally, depending on the resulting score, an assessment may be made as to whether or not the particular bubble shows evidence or an erasure or other artifact on the form.